#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct node *tree_ptr;		// node pointer
typedef struct node{
	tree_ptr llink;					// struct node has left-link part, right-link part, and key part
	int key;
	tree_ptr rlink;
};

typedef struct string *string_ptr;	// string pointer
typedef struct string {				// struct string has string name part and tree pointer part
	char stringname[10];
	tree_ptr link;
} string;


// function declarations
tree_ptr insert_node(int X, tree_ptr T),
		 Delete( int X, tree_ptr T),
		 Find( int X, tree_ptr T ),
		 FindMin( tree_ptr T ),
		 FindMax( tree_ptr T ),
		 DeleteAll(tree_ptr T),
		 copy(tree_ptr original) ;

void	preOrder(tree_ptr node),
		inOrder(tree_ptr node),
		postOrder(tree_ptr node),
		levelOrder(tree_ptr ptr),
		printofLevel(tree_ptr node, int selected_level, int cur_level);
		
int isEmpty(tree_ptr root),
	treeHeight(tree_ptr node),
	equal(tree_ptr first,tree_ptr second),
	bigger(int a, int b);
	
int main()
{
	string S[20];				// string array S[20]
	tree_ptr T;
	char choice[10];			// menu select
	int cur_index = 0;			// current index
	int key, i, cip;			// key input, iteration, a cipher
	int bst_no, location;		// BST number, location is used at insert
	int level;					

	char data[200];				// put input numbers at data
	char strName[30],			// put input string name at strName and strName2
		strName2[30];

	for(i = 0; i < 20; i++){	// all links of S is initialized NULL
		S[i].link = NULL;
	}
	
	do{
		printf("(1)Insert (2)Search (3)Delete (4)Height (5)Preorder (6)Inorder (7)Postorder (8)Level order (9)Print of level (10)Copy (11)Equal (12)Delete all (x)Exit\nChoice ? ");
		scanf("%s", choice);

		if(strcmp(choice,"x") == 0)		// choice is x, then finish
			break;


		switch(atoi(choice)){			// ascii to integer (string to integer)
		case 1:	 // insert
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){	// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("New Binary Search Tree\n");			// if there is no BST whose name is strName, then new BST!
				bst_no = cur_index;
				cur_index++;
				strcpy(S[bst_no].stringname, strName);
				T = S[bst_no].link;
			}

			fflush(stdin);
			
			printf("Type numbers to input : ");				// input numbers to input by string
			gets(data);

			location = 0;
			do{
				sscanf(&data[location], "%d", &key);		// put data one by one
				
				S[bst_no].link = insert_node(key, S[bst_no].link); // insert at BST
				
				for(cip = key ; cip!=0 ; cip = cip / 10){
					location++;									// find cipher
				}
				location++;

			}while(data[location-1] != NULL);

			printf("%s inserted into %s!!\n\n", data, strName);
			break;
			
		case 2:		// search
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){		// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n\n", strName);	// error message
				break;
			}

			printf("Type a number to search : ");
			scanf("%d", &key);

			if(Find(key, S[bst_no].link) != NULL)
				printf("%d is exist in %s!!\n\n", key, S[bst_no].stringname);
			else
				printf("%d is not exist in %s!!\n\n", key, S[bst_no].stringname);

			break;

		case 3:		// delete
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){		// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}

			printf("Type a number to delete : ");
			scanf("%d", &key);

			if(Find(key, S[bst_no].link)){							// if there is number to delete
				S[bst_no].link = Delete(key, S[bst_no].link);		// delete it
				printf("%d is deleted from %s!!\n\n", key, S[bst_no].stringname);
			}
			else													// else
				printf("%d is not exist in %s!!\n\n", key, S[bst_no].stringname);	// error message
			break;

		case 4:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}

			printf("Height of the BST1 : %d\n\n", treeHeight(S[bst_no].link));
			break;

		case 5:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}
			printf("Preorder Traversal!!\n");
			T = S[bst_no].link;
			preOrder(T);
			printf("\n\n");
			break;

		case 6:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}
			printf("Inorder Traversal!!\n");
			T = S[bst_no].link;
			inOrder(T);
			printf("\n\n");
			break;

		case 7:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}
			printf("Postorder Traversal!!\n");
			T = S[bst_no].link;
			postOrder(T);
			printf("\n\n");
			break;

		case 8:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}
			printf("Lever-order Traversal!!\n");
			T = S[bst_no].link;
			levelOrder(T);
			printf("\n\n");
			break;

		case 9:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){			// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}

			printf("Level : ");
			scanf("%d", &level);
			if(level >  treeHeight(S[bst_no].link))
				printf("Level can not be bigger than height of tree!!\n\n");
			else
				printofLevel(S[bst_no].link, level, 1);

			printf("\n\n");
			break;

		case 10:
			printf("Type the name of the original and new BST: : ");
			scanf("%s %s", strName2, strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName2) == 0){		// find if there is already BST whose name is strName2
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no original tree whose name is %s!\n", strName2);	// error message
				break;
			}
			strcpy(S[cur_index].stringname, strName);
			S[cur_index].link = copy(S[bst_no].link);
			cur_index++;
			printf("%s is copied from %s!!\n\n", strName, strName2);
			break;
			
		case 11:
			printf("Type two BSTs to compare : ");
			scanf("%s %s", strName, strName2);				
			
			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){		// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}	
			if(i == cur_index){
				printf("There is no original tree whose name is %s!\n", strName);	// error message
				break;
			}

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName2) == 0){		// find if there is already BST whose name is strName2
					break;
				}
			}
			if(i == cur_index){
				printf("There is no original tree whose name is %s!\n", strName2);	// error message
				break;
			}

			if(equal(S[bst_no].link, S[i].link))
				printf("%s and %s are equal!!\n\n", S[bst_no].stringname, S[i].stringname);
			else
				printf("%s and %s are not equal!!\n\n", S[bst_no].stringname, S[i].stringname);

			break;

		case 12:
			printf("Type the name of BST : ");
			scanf("%s", strName);

			for(i=0; i < cur_index ; i++){
				if(strcmp(S[i].stringname, strName) == 0){		// find if there is already BST whose name is strName
					bst_no = i;
					break;
				}
			}
			
			if(i == cur_index){
				printf("There is no Tree whose name is %s!\n", strName);	// error message
				break;
			}

			S[bst_no].link = DeleteAll(S[bst_no].link);
			
			printf("All nodes are deleted!!\n\n");
			break;

		default:
			printf("You choose wrong number\n\n");
			break;
		}
		
	}while(1);

	printf("Thank you for using this software!!\n");		// good bye
}

tree_ptr insert_node(int X, tree_ptr T)  
{  
	if( T == NULL )  
	{  
		/* Create and return a one-node tree */ 
		T = (tree_ptr)malloc( sizeof( struct node ) );  
		if( T == NULL )  
			printf( "Out of space!!!" );				// memory is full
		else 
		{  
			T->key = X;             
			T->llink = T->rlink = NULL; 
		}
	}  
	else {
		if( X < T->key )  
			T->llink = insert_node( X, T->llink );  
		else {
			if( X > T->key )  
				T->rlink = insert_node( X, T->rlink );
		}
	/* Else X is in the tree already; we'll do nothing */ 
	}
	return T;  // return tree_ptr T
}  

void inOrder(tree_ptr node)		// in-order : LVR
{
	if(node != NULL) {
		inOrder(node->llink);
		printf("%d  ", node->key);
		inOrder(node->rlink);
	}
}

void preOrder(tree_ptr node)	// pre-order : VLR
{
	if(node) {
		printf("%d  ", node->key);
		preOrder(node->llink);
		preOrder(node->rlink);
	}
}

void postOrder(tree_ptr node)	// post-order : LRV
{
	if(node) {
		postOrder(node->llink);
		postOrder(node->rlink);
		printf("%d  ", node->key);
	}
}

tree_ptr Find(int X, tree_ptr T )		// find recursively left part and right part
{
	if( T == NULL ){
		return NULL;
	}
	if( X == T->key)
		return T;
	else if( X < T->key )
		return Find( X, T->llink );
	else if( X > T->key )
		return Find( X, T->rlink );
}

tree_ptr FindMin( tree_ptr T )			// find minimum tree_ptr
{
	if( T == NULL )
		return NULL;
	else
		if( T->llink == NULL )
			return T;
		else
			return FindMin( T->llink );
}

tree_ptr FindMax( tree_ptr T )			// find maximum tree_ptr
{
	if( T != NULL )
		while( T->rlink != NULL )
			T = T->rlink;

	return T;
}

tree_ptr Delete( int X, tree_ptr T )
{
	tree_ptr TmpCell;

	if( T == NULL )
		printf( "Element not found" );
	else
		if( X < T->key )  /* Go left */
			T->llink = Delete( X, T->llink );
		else
			if( X > T->key )  /* Go right */
				T->rlink = Delete( X, T->rlink );
			else  /* Found element to be deleted */
				if( T->llink && T->rlink )  /* Two children */
				{
					/* Replace with smallest in right subtree */
					TmpCell = FindMin( T->rlink );
					T->key = TmpCell->key;
					T->rlink = Delete( T->key, T->rlink );
				}
				else  /* One or zero children */
				{
					TmpCell = T;
					if( T->llink == NULL ) /* Also handles 0 children */
						T = T->rlink;
					else if( T->rlink == NULL )
						T = T->llink;
					free( TmpCell );
				}

				return T;
}

tree_ptr DeleteAll(tree_ptr T)
{
	while(T != NULL)
		T = Delete(T->key, T);// delete nodes while T points NULL

	return T;
}

void levelOrder(tree_ptr ptr)
{
	int i;
	int front =0;
	int rear = 0;
	tree_ptr queue[100];			// queue

	for(i=0; i<100; i++)
		queue[i] = NULL;			// initialized by NULL

	if( !ptr )
		return;
	
	queue[rear++] = ptr;			// push

	while(1)
	{
		ptr = queue[front];			// pop
		front++;

		if(ptr)
		{
			printf("%d ", ptr->key);	
			
			if(ptr->llink)
			{
				queue[rear] = ptr->llink;	// push left child
				rear++;
			}
			if(ptr->rlink)	
			{
				queue[rear] = ptr->rlink;	// push right child
				rear++;
			}
			
		}
		else 
			break;
	}
}

int equal(tree_ptr first,tree_ptr second)
{
	return ((!first && !second) ||	(first && second && (first->key == second->key)
		&& equal(first->llink, second->llink)
		&& equal(first->rlink, second->rlink)));
}

tree_ptr copy(tree_ptr original) {
	tree_ptr temp;
	if (original) {
		temp = (tree_ptr)malloc(sizeof(struct node));
		if (!temp) 
			printf("Memory is full!!\n\n");

		temp->llink = copy(original->llink);
		temp->rlink = copy(original->rlink);
		temp->key = original->key;
		return temp;
	}
	return NULL;
}

int treeHeight(tree_ptr node)
{
	if(!node)
		return 0;
	else
		return 1+bigger(treeHeight(node->rlink), treeHeight(node->llink));
}

int bigger(int a, int b)
{
	return a>b?a:b;
}

void printofLevel(tree_ptr node, int selected_level, int cur_level)
{
	if(!node)
		return;
	else{
		if(selected_level == cur_level)
			printf("%d  ", node->key);
		else{
			printofLevel(node->llink, selected_level, cur_level+1);
			printofLevel(node->rlink, selected_level, cur_level+1);

		}
	}
}